\begin{usection}{10201. Adventures in moving}
	\url{http://uva.onlinejudge.org/external/102/10201.html}\\
	
	El problema consiste, dada una distancia que se quiere recorrer y una lista de estaciones de servicio en el camino (con distintos precios), minimizar el costo de las recargas de combustible necesarias para llegar a destino.

	\begin{usubsection}{Idea}
		Ideamos una solución basada en un algoritmo goloso.
		
		Como primer paso, el algoritmo verfica que $\forall\ estacion\ e_k,\ con\ 0\leq k<n$ se cumpla que $pos(e_{k+1})-pos(e_k)\leq 200$, siendo $n$ la cantidad total de estaciones en el trayecto, y $pos()$ la distancia de una estación en relación al origen.
		Con esto se busca verificar que la distancia entre dos estaciones sucesivas no sea mayor a la capacidad del tanque, ya que cuando esto no ocurre el problema no tiene solución\footnote{Esto se debe a que el consumo del vehículo es de 1km/litro, con lo cual, es necesario que la distancia entre dos estaciones aledañas no supere la capacidad del tanque.} En caso de no verificarse lo anteior el output del programa para esa instancia del problema es ``\texttt{Impossible}''.
		
		Una vez seguro de que la instancia tiene solución, el algortimo procede del siguiente modo. Se generan tres variables: \textit{gasto, nafta, pos}, las cuales representan el gasto por recargas de combustible, los litros de nafta restantes en el tanque y la posición del vehículo desde el origen respectivamente. Seguidamente avanza hasta la primera estación, registrando $pos(e_0)$ en \textit{pos} y restando a \textit{nafta} el consumo efectuado. A partir de allí busca entre las estaciones siguientes (que estén a menos de 200km) la estacion con el menor precio por litro.
		
		Si el algortimo no encuentra ninguna estación más barata en una distancia menor a 200 km en relación a aquella en la que se encuentra, entonces llena el tanque en la estación actual y avanza el vehículo a la próxima estación. Actualiza \textit{gasto}, \textit{pos} y \textit{nafta}.
		
		En cambio, si logra encontrar una estación más barata y cuya distancia sea menor o igual a los 200 km, entonces carga, de ser necesario, la cantidad justa para poder llegar hasta esa estación hallada y avanza el vehículo hasta esa estación.
		
		Finalmente, el algortimo repite el proceso hasta haber recorrido todas las estaciones de servicio y devuelve como resultado el valor de la variable  \textit{gasto}.
		
		Para asegurarnos de que llegue a la última estación con medio tanque (requerimiento del problema), agregamos una estación en $dist\_total+100$ donde la nafta es gratis. De esta forma tiene que llegar hasta esta estación, y llega con lo mínimo posible.
	\end{usubsection}

	\begin{usubsection}{Complejidad}
	\paragraph{}
		Para cada estación, se busca entre las estaciones restantes aquella  una con menor precio y que no diste en más de 200 km. Es claro que comparar los precios entre estaciones es \Ode{1}. Luego, el peor escenario posible es aquel en el que las estaciones están ordenadas por precio de manera creciente, y en donde la primera estación dista de la última en a lo sumo 200 km. De este modo, el algoritmo debe para cada estación, recorrer todas las que le siguen para poder decidir que hacer.
	\paragraph{}
		Observese entonces que la cantidad de operaciones que realiza el algoritmo es de la forma:
		\begin{center}
			\begin{pseudo}
				\FOR $i\gets 1 \TO n$\\
				\tab \FOR $k\gets i \TO n$
			\end{pseudo}
		\end{center}
de donde se puede concluir que la complejidad del mismo es \Ode{n^2}.
		
	\end{usubsection}

\end{usection}

